import java.awt.Canvas;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;

import javax.swing.JFrame;
import javax.swing.JOptionPane;


public class FGMain extends Canvas {
	
	public class Grid implements Comparable<Grid> {
		
		int[] grid;
		int g_score;
		Grid cameFrom = null;
		int[] goal = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0};
		
		Grid() {
			
			grid = new int[16];
			for (int i = 0; i < 15; i++) {
				grid[i] = i+1;
			}
			grid[15]=0;
			
		}
		
		Grid(Grid fromGrid, int swapIndex, int forIndex) {
			
			grid = fromGrid.grid.clone();
			
			int temp = grid[swapIndex];
			grid[swapIndex] = grid[forIndex];
			grid[forIndex] = temp;
			
		}
		
		void setGrid(int[] userGrid) {
			grid = userGrid.clone();
		}
		
		List<Grid> getNeighbors() {
			
			List<Grid> neighbors = new ArrayList<Grid>();
			
			// 2, 3 or 4
			
			int spaceIndex = 0;
			// find space
			for (int i = 0; i < 16; i++) {
				if (grid[i] == 0) {
					spaceIndex = i;
					break;
				}
			}
			
			// shift space up
			if (spaceIndex > 3) {
				neighbors.add(new Grid(this, spaceIndex, spaceIndex-4));
			}
			// shift space right
			if ((spaceIndex+1)%4 != 0) {
				neighbors.add(new Grid(this, spaceIndex, spaceIndex+1));
			}
			
			// shift space down
			if (spaceIndex < 12) {
				neighbors.add(new Grid(this, spaceIndex, spaceIndex+4));
			}
			
			// shift space left
			if ((spaceIndex)%4 != 0) {
				neighbors.add(new Grid(this, spaceIndex, spaceIndex-1));
			}
			
			return neighbors;	
		}
		
		public List<Grid> solve() {
			
			List<Grid> solution = null;
			
			TreeSet<Grid> visited = new TreeSet<Grid>();
			TreeSet<Grid> openset = new TreeSet<Grid>();
			
			openset.add(this);
			this.g_score = 0;
			
			while (!openset.isEmpty()) {
				
				Grid lowest = null;
				int lowestF = Integer.MAX_VALUE;
				for (Grid unvisited : openset) {
					if (unvisited.f_score() < lowestF) {
						lowestF = unvisited.f_score();
						lowest = unvisited;
					}
				}
				
				if (Arrays.equals(lowest.grid, goal)) {
					solution = new ArrayList<Grid>();
					while (lowest.cameFrom != null) {
						solution.add(0, lowest);
						lowest = lowest.cameFrom;
					}
					return solution;
				}
				
				openset.remove(lowest);
				visited.add(lowest);
				
				for (Grid neighbor : lowest.getNeighbors()) {
					
					neighbor.g_score = lowest.g_score + 1;
					neighbor.cameFrom = lowest;
					
					boolean discard = false;
					for (Grid x : visited) {
						if (x.compareTo(neighbor)==0 && x.g_score <= neighbor.g_score) {
							discard = true;
							break;
						}
					}
					
					for (Grid x : openset) {
						if (x.compareTo(neighbor)==0 && x.g_score <= neighbor.g_score) {
							discard = true;
							break;
						}
					}
					
					if (discard) {
						continue;
					}
					
					openset.remove(neighbor);
					visited.remove(neighbor);
					openset.add(neighbor);
					
				}
				
			}
			
			return solution;
			
		}
		
		int f_score() {
			return g_score + h_score();
		}
		
		int h_score() {
			
			int rating = 0;
			
			for (int i = 0; i < 16; i++) {
				
				// correct location
				int corX = (grid[i] == 0 ? 3 : (i-1) % 4);
				int corY = (grid[i] == 0 ? 3 : (i-1) / 4);
				
				// actual
				int actX = i % 4;
				int actY = i / 4;
				
				// add manhattan distance
				rating+= Math.abs(corX - actX) + Math.abs(corY - actY);	
			}	
			return rating;
		}

		@Override
		public int compareTo(Grid o) {
			boolean equalFlag = true;
			for (int i = 0; i < 16; i++) {
				if (grid[i] != o.grid[i]) {
					equalFlag = false;
				}
			}
			
			if (equalFlag)
				return 0;
			
			if (this.f_score() < o.f_score()) {
				return 1;
			} else {
				return -1;
			}
		}
		
		@Override
		public String toString() {
			return Arrays.toString(grid);
		}
 		
	}

	private static final long serialVersionUID = 1L;
	int[] currentGrid = new int[16];
	Color[] colors = new Color[16];
	JFrame frame;
	
	FGMain() {
		
		Dimension size = new Dimension(545, 545);
		
		setPreferredSize(size);
		
		Random r = new Random();
		for (int i = 0; i < 16; i++) {
			colors[i] = new Color(r.nextInt(0xffffff));
		}
		colors[0] = Color.DARK_GRAY;
		
		frame = new JFrame();
		frame.setTitle("15-mäng (c) Karl Puusepp");
		frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		frame.add(this);
		frame.pack();
		frame.setResizable(false);
		frame.setLocationRelativeTo(null);
		frame.setVisible(true);
		
		Grid g = new Grid();
		
		int[] inputGrid = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 0, 13, 14, 15};
		
		
		
		try {
			
			String[] inputStrings = JOptionPane.showInputDialog(null, 
					"Palun sisesta mängu algseis kujul '1, 2, ... , 15, 0'. \nNull tähistab tühja ruutu.", "15-mäng (c) Karl Puusepp", 
					JOptionPane.INFORMATION_MESSAGE).split("[ ,;]+");
			
			int i=0;
			for (String str : inputStrings) {
				inputGrid[i] = Integer.parseInt(str);
				i++;
			}
			
			g.setGrid(inputGrid);
			currentGrid = inputGrid.clone();
			List<Grid> solution = g.solve();
			if (solution != null && i == 16) {
				System.out.println();
				this.repaint();
				JOptionPane.showMessageDialog(null, 
						"Lahendus leitud! Alustame selle kuvamist.", "15-mäng (c) Karl Puusepp",
						JOptionPane.INFORMATION_MESSAGE);
				animate(solution);
			} else {
				System.out.println(i);
				throw new Exception("Lahendust ei leitud.");
				
			}
			
		} catch (Exception e) {
			
			JOptionPane.showMessageDialog(null, 
					"Viga!\n"+e.getMessage(), "15-mäng (c) Karl Puusepp",
					JOptionPane.ERROR_MESSAGE);
			
		}
		
		
		
	}
	
	void animate(List<Grid> solution) {
		
		try {
			Thread.sleep(1000);
		} catch (InterruptedException e1) {
		}
		
		for (Grid sol : solution) {
			this.currentGrid = sol.grid;
			this.validate();
			this.repaint();
			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {}
			
		}
		
		System.out.println();
		JOptionPane.showMessageDialog(null, 
				"Ja nii lihtne see oligi! :)", "15-mäng (c) Karl Puusepp",
				JOptionPane.INFORMATION_MESSAGE);
		
	}
	
	Color getColorForSquare(int sq) {
		
		return colors[sq];
		
	}
	
	@Override
	public void paint(Graphics g) {
		
		g.setColor(Color.DARK_GRAY);
		g.fillRect(0, 0, 545, 545);
		
		int k = 0;
		
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int square = currentGrid[k];
				g.setColor(getColorForSquare(square));
				g.fillRect(5+j*135, 5+i*135, 130, 130);
				g.setColor(Color.BLACK);
				g.setFont(getFont());
				if (square != 0)
					g.drawString(square+"", 70+j*135, 70+i*135);
				
				k++;
			}
		}
		
	}
	
	public static void main(String[] args) {
		new FGMain();

	}

}
